package com.markus.code.图.图1;

import java.util.*;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 12:14
 * todo:
 */
public class GraphTopologySort {
    public List<Node> topology(Graph graph){
        List<Node> res = new ArrayList<>();
        //装载入度的map结构
        HashMap<Node,Integer> inMap = new HashMap<>();
        HashSet<Node> set = new HashSet<>();
        for (Node node : graph.nodes.values()){
            Integer in = node.in;
            inMap.put(node,in);
        }
        while(set.size() < inMap.size()){
            for (Map.Entry<Node, Integer> entry : inMap.entrySet()) {
                Node key = entry.getKey();
                Integer value = entry.getValue();
                //再次找入度为0的节点
                if (value == 0 && !set.contains(key)){
                    res.add(key);
                    set.add(key);
                    for (Node next : key.nexts) {
                        inMap.put(next,inMap.get(next)-1);
                    }
                }
            }
        }
        return res;
    }
}
